#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//int main()
//{
//	int a, b, c, d;
//	while (scanf("%d", &a) == 1)
//	{
//		b = 0;
//		c = a;
//		d = 0;
//		while (a / 2)
//		{
//			b = a / 2;
//			c += b;
//			d += a % 2;
//			a /= 2;
//			a += d;
//			d = 0;
//		}
//		printf("%d\n",c);
//	}
//}

//bool Find(int target, int** array, int arrayRowLen, int* arrayColLen) {
//    // write code here
//    int l = 0;
//    int w = 0;
//    while (array[l][(*arrayColLen) - 1] < target)
//    {
//        l++;
//        if (l == arrayRowLen)
//        {
//            return false;
//        }
//    }
//    if (array[l][(*arrayColLen) - 1] == target)
//    {
//        return true;
//    }
//    while (array[l][w] < target)
//    {
//        w++;
//    }
//    if (array[l][w] == target)
//    {
//        return true;
//    }
//    else {
//        return false;
//    }
//}

//int main()
//{
//	char arr[100] = " ";
//	char* s = arr;
//    int i = 0;
//    int n = 0;
//    while (*(s + i))
//    {
//        if (*(s + i) == ' ')
//        {
//            n += 2;
//        }
//        i++;
//    }
//    i += n;
//    for (n = abs(i - n); n >= 0; n--)
//    {
//        if (s[n] == ' ')
//        {
//            s[i] = '0';
//            i--;
//            s[i] = '2';
//            i--;
//            s[i] = '%';
//            i--;
//        }
//        else {
//            s[i] = s[n];
//            i--;
//        }
//    }
//    printf("%s", arr);
//	return 0;
//}

//int* printListFromTailToHead(struct ListNode* listNode, int* returnSize)
//{
//    // write code here
//    struct ListNode* p = listNode;
//    struct ListNode* k = listNode;
//    int i = 0;
//    if (listNode == NULL)
//    {
//        return returnSize;
//    }
//    while (p->next)
//    {
//        p = p->next;
//    }
//    while (p != listNode)
//    {
//        while (k->next != p)
//        {
//            k = k->next;
//        }
//        *(returnSize + i) = p->val;
//        p = k;
//        i++;
//    }
//    *(returnSize + i) = p->val;
//    return returnSize;
//}

//struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
//{
//    if (l1 == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* n1 = l1;
//    struct ListNode* n2 = l2;
//    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* n4 = n3;
//    while (n1 || n2)
//    {
//        if (n1 == NULL)
//        {
//            n4->val = n2->val;
//            n4->next = (struct ListNode*)malloc(sizeof(struct ListNode));
//            n4 = n4->next;
//            n2 = n2->next;
//        }
//        else if (n2 == NULL)
//        {
//            n4->val = n1->val;
//            n4->next = (struct ListNode*)malloc(sizeof(struct ListNode));
//            n4 = n4->next;
//            n1 = n1->next;
//        }
//        else
//        {
//            if ((n1->val) + (n2->val) + (n4->val) > 9)
//            {
//                n4->val = ((n1->val) + (n2->val) + (n4->val)) % 10;
//                n4->next = (struct ListNode*)malloc(sizeof(struct ListNode));
//                n4 = n4->next;
//                n1 = n1->next;
//                n2 = n2->next;
//                n4->val = 1;
//            }
//            else
//            {
//                n4->val = ((n1->val) + (n2->val) + (n4->val)) % 10;
//                n4->next = (struct ListNode*)malloc(sizeof(struct ListNode));
//                n4 = n4->next;
//                n1 = n1->next;
//                n2 = n2->next;
//                n4->val = 0;
//            }
//        }
//    }
//    if (n4->val == 0)
//    {
//        free(n4);
//        n4 = NULL;
//    }
//    return n3;
//}

//int* twoSum(int* nums, int numsSize, int target, int* returnSize)
//{
//    int m = 0, n = 0;
//    returnSize = NULL;
//    for (m = 0; m < numsSize - 1; m++)
//    {
//        for (n = m + 1; n < numsSize; n++)
//        {
//            if (nums[m] + nums[n] == target)
//            {
//                returnSize = (int*)malloc(sizeof(int) * 2);
//                returnSize[0] = m;
//                returnSize[1] = n;
//                return returnSize;
//            }
//        }
//    }
//    return returnSize;
//}